package demo.practice.leetcode_trie;

public class P421 {

    class Node {
        public Node left;
        public Node right;

        public Node() {
        }

    }


    public static void main(String[] args) {
        P421 p421= new P421();
        p421.findMaximumXOR(new int[]{3, 10, 5, 25, 2, 8});
    }

    public int findMaximumXOR(int[] nums) {
        // 二叉树模拟 字典树,左为1，右为0
        // 树初始化
        Node root = new Node();
        // 小于2^30时 使用30位作为掩码
        int mask = 1 << 31;
        for (int i : nums) {
            String s = Integer.toBinaryString(mask | i);
            Node cur = root;
            // 30位分解
            for (char c : s.toCharArray()) {
                if (c == '0') {
                    if (cur.right == null) {
                        cur.right = new Node();
                    }
                    cur = cur.right;
                } else {
                    if (cur.left == null) {
                        cur.left = new Node();
                    }
                    cur = cur.left;
                }
            }
        }
        int max = Integer.MIN_VALUE;
        // 遍历树，贪心规则 每遍历一位时尽量XOR为1
        for (int i : nums) {
            String s = Integer.toBinaryString(mask | i);
            Node cur = root;
            StringBuilder xor = new StringBuilder();
            for (char c : s.toCharArray()) {
                if (c == '0') {
                    if (cur.left != null) {
                        cur = cur.left;
                        xor.append("1");
                    } else {
                        cur = cur.right;
                        xor.append("0");
                    }
                } else {
                    if (cur.right != null) {
                        cur = cur.right;
                        xor.append("1");
                    } else {
                        cur = cur.left;
                        xor.append("0");
                    }
                }
            }
            int tem = Integer.parseInt(xor.toString(), 2);
            max = Math.max(max, tem);
        }
        return max;
    }

}
